package puzzle.projecteuler.p300;

import astudy.util.AdvMath;



public class Problem231C {
	

	/**
	 * answer	: 7526965179680
	 * time cost: 3078 ms
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
	
		long s = System.currentTimeMillis();
		
		long c = 0;
		Integer[] primes = AdvMath.primes(20000000);
		for (Integer p: primes) {
			c += p * power(20000000, 15000000, p);
		}
		System.out.println(c);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	/**
	 * power of p in n!
	 * @param n
	 * @param p
	 * @return
	 */
	private static long power(long n, long p) {
		
		long c = 0;
		do {
			n /= p;
			c += n;
		} while (n > 0);
		return c;
	}
	
	/**
	 * power of p in C(m,n)
	 * @param n
	 * @param p
	 * @return
	 */
	private static long power(long m, long n, long p) {

		return power(m, p) - power(n, p) - power(m-n, p);
	}
}
